package leetcode_jz_offer.day4_array;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
 * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字
 * 链接：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof
 **/
public class Num53_2_0到n减1中缺失的数字 {

    public  int missingNumber(int[] nums) {

        //方法2：哈希
        HashSet<Integer> set=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {//将数组内容全放在Set表中
            set.add(nums[i]);
        }
        int res=-1;
        for (int i = 0; i < nums.length + 1; i++) {//遍历0-n-1的所有数字（一共n个数，所以需要给nums.length+1）
            if(!set.contains(i)){
                res=i;
                break;
            }
        }
        return res;
        
        //方法一：排序
//        Arrays.sort(nums);
//        int n=nums.length+1;
//        for (int i = 0; i < n - 1; i++) {
//            if(nums[i]!=i){
//                return i;
//            }
//        }
//        return n-1;
    }
}
